package q2200_findKDistantIndices;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    /*
    思路在于做标记 第一次遍历的时候 如果发现有一个数是key
    那么就将其前面k范围内的所有数字标记为-1 除了当前数字
    然后再遍历一次 又将其后面k范围内所有数字标记
    这样就避免了如果一个key能够包含的k范围很大 而覆盖了另一个后面的key 导致本来能够达到的位置没有被包含
     */
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == key) {
                for (int j = 1; j <= k && i >= j; j++) nums[i - j] = -1;
                // for (int j = 1; j <= k && i + j < nums.length; j++) nums[i + j] = -1;
                // i += k;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == key) {
                // for (int j = 0; j <= k && i >= j; j++) nums[i - j] = -1;
                for (int j = 0; j <= k && i + j < nums.length; j++) nums[i + j] = -1;
                i += k;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == -1) res.add(i);
        }
        return res;
    }
}
